home *** CD-ROM | disk | FTP | other *** search
/ Games of Daze / Infomagic - Games of Daze (Summer 1995) (Disc 1 of 2).iso / x2ftp / msdos / source / snip9503 / eval.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-03-14  |  13.1 KB  |  458 lines
  1. /************************************************************************/
  2. /*                                                                      */
  3. /*  EVALUATE.C - A simple mathematical expression evaluator in C        */
  4. /*                                                                      */
  5. /*  operators supported: Operator               Precedence              */
  6. /*                                                                      */
  7. /*                         (                     Lowest                 */
  8. /*                         )                     Highest                */
  9. /*                         +   (addition)        Low                    */
  10. /*                         -   (subtraction)     Low                    */
  11. /*                         *   (multiplication)  Medium                 */
  12. /*                         /   (division)        Medium                 */
  13. /*                         \   (modulus)         High                   */
  14. /*                         ^   (exponentiation)  High                   */
  15. /*                         sin(                  Lowest                 */
  16. /*                         cos(                  Lowest                 */
  17. /*                         atan(                 Lowest                 */
  18. /*                         abs(                  Lowest                 */
  19. /*                         sqrt(                 Lowest                 */
  20. /*                         ln(                   Lowest                 */
  21. /*                         exp(                  Lowest                 */
  22. /*                                                                      */
  23. /*  constants supported: pi                                             */
  24. /*                                                                      */
  25. /*  Original Copyright 1991-93 by Robert B. Stout as part of            */
  26. /*  the MicroFirm Function Library (MFL)                                */
  27. /*                                                                      */
  28. /*  This subset version is hereby donated to the public domain.         */
  29. /*  Requires RMALLWS.C, also in SNIPPETS.                               */
  30. /*                                                                      */
  31. /************************************************************************/
  32.  
  33. #include <stdlib.h>
  34. #include <string.h>
  35. #include <ctype.h>
  36. #include <math.h>
  37.  
  38. #define LAST_CHAR(string) (((char *)string)[strlen(string)-1])
  39.  
  40. struct operator {
  41.       char        token;
  42.       char       *tag;
  43.       size_t      taglen;
  44.       int         precedence;
  45. };
  46.  
  47. #define NUL '\0'
  48.  
  49. typedef enum {R_ERROR = -2 /* range */, ERROR /* syntax */, SUCCESS} STATUS;
  50.  
  51. static struct operator verbs[] = {
  52.       {'+',  "+",       1, 2 },
  53.       {'-',  "-",       1, 3 },
  54.       {'*',  "*",       1, 4 },
  55.       {'/',  "/",       1, 5 },
  56.       {'\\', "\\",      1, 5 },
  57.       {'^',  "^",       1, 6 },
  58.       {'(',  "(",       1, 0 },
  59.       {')',  ")",       1, 99},
  60.       {'S',  "SIN(",    4, 0 },
  61.       {'C',  "COS(",    4, 0 },
  62.       {'A',  "ABS(",    4, 0 },
  63.       {'L',  "LN(",     3, 0 },
  64.       {'E',  "EXP(",    4, 0 },
  65.       {'t',  "ATAN(",   5, 0 },
  66.       {'s',  "SQRT(",   5, 0 },
  67.       {NUL,  NULL,      0, 0 }
  68. };
  69.  
  70. static char   op_stack[256];                    /* Operator stack       */
  71. static double arg_stack[256];                   /* Argument stack       */
  72. static char   token[256];                       /* Token buffer         */
  73. static int    op_sptr,                          /* op_stack pointer     */
  74.               arg_sptr,                         /* arg_stack pointer    */
  75.               parens,                           /* Nesting level        */
  76.               state;                            /* 0 = Awaiting expression
  77.                                                    1 = Awaiting operator
  78.                                                 */
  79. const double Pi = 3.14159265358979323846;
  80.  
  81. int                     evaluate(char *, double *);
  82.  
  83. char                   *rmallws(char *);        /* Also in SNIPPETS     */
  84.  
  85. static int              do_op(void);
  86. static int              do_paren(void);
  87. static void             push_op(char);
  88. static void             push_arg(double);
  89. static int              pop_arg(double *);
  90. static int              pop_op(int *);
  91. static char            *get_exp(char *);
  92. static struct operator *get_op(char *);
  93. static int              getprec(char);
  94. static int              getTOSprec(void);
  95.  
  96. #ifdef TEST
  97.  
  98. #include <stdio.h>
  99.  
  100. main(int argc, char *argv[])
  101. {
  102.       int retval;
  103.       double val;
  104.  
  105.       printf("evaluate(%s) ", argv[1]);
  106.       printf("returned %d\n", retval = evaluate(argv[1], &val));
  107.       if (0 == retval)
  108.             printf("val = %f\n", val);
  109.       return 0;
  110. }
  111.  
  112. #endif
  113.  
  114. /************************************************************************/
  115. /*                                                                      */
  116. /*  evaluate()                                                          */
  117. /*                                                                      */
  118. /*  Evaluates an ASCII mathematical expression.                         */
  119. /*                                                                      */
  120. /*  Arguments: 1 - String to evaluate                                   */
  121. /*             2 - Storage to receive double result                     */
  122. /*                                                                      */
  123. /*  Returns: SUCCESS if successful                                      */
  124. /*           ERROR if syntax error                                      */
  125. /*           R_ERROR if runtime error                                   */
  126. /*                                                                      */
  127. /*  Side effects: Removes all whitespace from the string and converts   */
  128. /*                it to U.C.                                            */
  129. /*                                                                      */
  130. /************************************************************************/
  131.  
  132. int evaluate(char *line, double *val)
  133. {
  134.       double arg;
  135.       char *ptr = line, *str, *endptr;
  136.       int ercode;
  137.       struct operator *op;
  138.  
  139.       strupr(line);
  140.       rmallws(line);
  141.       state = op_sptr = arg_sptr = parens = 0;
  142.  
  143.       while (*ptr)
  144.       {
  145.             switch (state)
  146.             {
  147.             case 0:
  148.                   if (NULL != (str = get_exp(ptr)))
  149.                   {
  150.                         if (NULL != (op = get_op(str)) &&
  151.                               strlen(str) == op->taglen)
  152.                         {
  153.                               push_op(op->token);
  154.                               ptr += op->taglen;
  155.                               break;
  156.                         }
  157.  
  158.                         if (SUCCESS == strcmp(str, "-"))
  159.                         {
  160.                               push_op(*str);
  161.                               ++ptr;
  162.                               break;
  163.                         }
  164.  
  165.                         if (SUCCESS == strcmp(str, "PI"))
  166.                               push_arg(Pi);
  167.  
  168.                         else
  169.                         {
  170.                               if (0.0 == (arg = strtod(str, &endptr)) &&
  171.                                     NULL == strchr(str, '0'))
  172.                               {
  173.                                     return ERROR;
  174.                               }
  175.                               push_arg(arg);
  176.                         }
  177.                         ptr += strlen(str);
  178.                   }
  179.                   else  return ERROR;
  180.  
  181.                   state = 1;
  182.                   break;
  183.  
  184.             case 1:
  185.                   if (NULL != (op = get_op(ptr)))
  186.                   {
  187.                         if (')' == *ptr)
  188.                         {
  189.                               if (SUCCESS > (ercode = do_paren()))
  190.                                     return ercode;
  191.                         }
  192.                         else
  193.                         {
  194.                               while (op_sptr &&
  195.                                     op->precedence <= getTOSprec())
  196.                               {
  197.                                     do_op();
  198.                               }
  199.                               push_op(op->token);
  200.                               state = 0;
  201.                         }
  202.  
  203.                         ptr += op->taglen;
  204.                   }
  205.                   else  return ERROR;
  206.  
  207.                   break;
  208.             }
  209.       }
  210.  
  211.       while (1 < arg_sptr)
  212.       {
  213.             if (SUCCESS > (ercode = do_op()))
  214.                   return ercode;
  215.       }
  216.       if (!op_sptr)
  217.             return pop_arg(val);
  218.       else  return ERROR;
  219. }
  220.  
  221. /*
  222. **  Evaluate stacked arguments and operands
  223. */
  224.  
  225. static int do_op(void)
  226. {
  227.       double arg1, arg2;
  228.       int op;
  229.  
  230.       if (ERROR == pop_op(&op))
  231.             return ERROR;
  232.  
  233.       pop_arg(&arg1);
  234.       pop_arg(&arg2);
  235.  
  236.       switch (op)
  237.       {
  238.       case '+':
  239.             push_arg(arg2 + arg1);
  240.             break;
  241.  
  242.       case '-':
  243.             push_arg(arg2 - arg1);
  244.             break;
  245.  
  246.       case '*':
  247.             push_arg(arg2 * arg1);
  248.             break;
  249.  
  250.       case '/':
  251.             if (0.0 == arg1)
  252.                   return R_ERROR;
  253.             push_arg(arg2 / arg1);
  254.             break;
  255.  
  256.       case '\\':
  257.             if (0.0 == arg1)
  258.                   return R_ERROR;
  259.             push_arg(fmod(arg2, arg1));
  260.             break;
  261.  
  262.       case '^':
  263.             push_arg(pow(arg2, arg1));
  264.             break;
  265.  
  266.       case 't':
  267.             ++arg_sptr;
  268.             push_arg(atan(arg1));
  269.             break;
  270.  
  271.       case 'S':
  272.             ++arg_sptr;
  273.             push_arg(sin(arg1));
  274.             break;
  275.  
  276.       case 's':
  277.             if (0.0 > arg2)
  278.                   return R_ERROR;
  279.             ++arg_sptr;
  280.             push_arg(sqrt(arg1));
  281.             break;
  282.  
  283.       case 'C':
  284.             ++arg_sptr;
  285.             push_arg(cos(arg1));
  286.             break;
  287.  
  288.       case 'A':
  289.             ++arg_sptr;
  290.             push_arg(fabs(arg1));
  291.             break;
  292.  
  293.       case 'L':
  294.             if (0.0 < arg1)
  295.             {
  296.                   ++arg_sptr;
  297.                   push_arg(log(arg1));
  298.                   break;
  299.             }
  300.             else  return R_ERROR;
  301.  
  302.       case 'E':
  303.             ++arg_sptr;
  304.             push_arg(exp(arg1));
  305.             break;
  306.  
  307.       case '(':
  308.             arg_sptr += 2;
  309.             break;
  310.  
  311.       default:
  312.             return ERROR;
  313.       }
  314.       if (1 > arg_sptr)
  315.             return ERROR;
  316.       else  return op;
  317. }
  318.  
  319. /*
  320. **  Evaluate one level
  321. */
  322.  
  323. static int do_paren(void)
  324. {
  325.       int op;
  326.  
  327.       if (1 > parens--)
  328.             return ERROR;
  329.       do
  330.       {
  331.             if (SUCCESS > (op = do_op()))
  332.                   break;
  333.       } while (getprec((char)op));
  334.       return op;
  335. }
  336.  
  337. /*
  338. **  Stack operations
  339. */
  340.  
  341. static void push_op(char op)
  342. {
  343.       if (!getprec(op))
  344.             ++parens;
  345.       op_stack[op_sptr++] = op;
  346. }
  347.  
  348. static void push_arg(double arg)
  349. {
  350.       arg_stack[arg_sptr++] = arg;
  351. }
  352.  
  353. static int pop_arg(double *arg)
  354. {
  355.       *arg = arg_stack[--arg_sptr];
  356.       if (0 > arg_sptr)
  357.             return ERROR;
  358.       else  return SUCCESS;
  359. }
  360.  
  361. static int pop_op(int *op)
  362. {
  363.       if (!op_sptr)
  364.             return ERROR;
  365.       *op = op_stack[--op_sptr];
  366.       return SUCCESS;
  367. }
  368.  
  369. /*
  370. **  Get an expression
  371. */
  372.  
  373. static char * get_exp(char *str)
  374. {
  375.       char *ptr = str, *tptr = token;
  376.       struct operator *op;
  377.  
  378.       if (SUCCESS == strncmp(str, "PI", 2))
  379.             return strcpy(token, "PI");
  380.  
  381.  
  382.       while (*ptr)
  383.       {
  384.             if (NULL != (op = get_op(ptr)))
  385.             {
  386.                   if ('-' == *ptr)
  387.                   {
  388.                         if (str != ptr && 'E' != ptr[-1])
  389.                               break;
  390.                         if (str == ptr && !isdigit(ptr[1]) && '.' != ptr[1])
  391.                         {
  392.                               push_arg(0.0);
  393.                               strcpy(token, op->tag);
  394.                               return token;
  395.                         }
  396.                   }
  397.  
  398.                   else if (str == ptr)
  399.                   {
  400.                         strcpy(token, op->tag);
  401.                         return token;
  402.                   }
  403.  
  404.                   else break;
  405.             }
  406.  
  407.             *tptr++ = *ptr++;
  408.       }
  409.       *tptr = NUL;
  410.  
  411.       return token;
  412. }
  413.  
  414. /*
  415. **  Get an operator
  416. */
  417.  
  418. static struct operator * get_op(char *str)
  419. {
  420.       struct operator *op;
  421.  
  422.       for (op = verbs; op->token; ++op)
  423.       {
  424.             if (SUCCESS == strncmp(str, op->tag, op->taglen))
  425.                   return op;
  426.       }
  427.       return NULL;
  428. }
  429.  
  430. /*
  431. **  Get precedence of a token
  432. */
  433.  
  434. static int getprec(char token)
  435. {
  436.       struct operator *op;
  437.  
  438.       for (op = verbs; op->token; ++op)
  439.       {
  440.             if (token == op->token)
  441.                   break;
  442.       }
  443.       if (op->token)
  444.             return op->precedence;
  445.       else  return 0;
  446. }
  447.  
  448. /*
  449. **  Get precedence of TOS token
  450. */
  451.  
  452. static int getTOSprec(void)
  453. {
  454.       if (!op_sptr)
  455.             return 0;
  456.       return getprec(op_stack[op_sptr - 1]);
  457. }
  458.